package 校招笔试.携程笔试;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/8 15:03
 */
public class 一轮第四题 {
    /*
游游正在逛超市，有n个商品摆成排，第个商品的价格为ai,游游对它的真爱度为b。所有商品的价格都是偶数。

超市开展了一个活动， 当游游花费原价买了一件商品时，她可以用半价买下一件右边相邻的商品(也可以用原价购买，这样该商品右边的商品就有 一次享受半价的机会) 。但如果游游半价购买了一件商品， 那么下一件右边相邻的商品只能原价购买。

换言之，如果游游想要半价买某一件商品，必须先用原价买下它相邻的左边的那个商品。

游游初始的钱为 x，她想要买的商品的喜爱度总和尽可能大，但总价格不能超过 x，你能帮帮她计算最大的喜爱度总和吗?

n x a大于1 小于 1000

b大于1小于 10e9

数据 范围  ： n,x,a[i]  ∈ [1 , 1000] ;
    b ∈ [1, 1e ^ 9]
 */
    /*
       flag : 表示 对上一个商品的 操作状态
       index : 表示 正在 处理 当前 index
       rest : 在 当前 index 下, 还剩余的 金额
     */
    public int recursion(int index,int rest,int flag,int nums[][]){
        if(rest <= 0 || index == nums.length){
            return 0;
        }
        int ans1 = recursion(index + 1,rest,0,nums),ans2 = 0;
        if(flag == 0){ // 0 表示 上一个 商品, 状态 , 未 买 or 半价 购买 (无论 哪一种情况, flag == 0 ,时 当前 index 可以为, 不买  or 原价 买!)
            ans2 = recursion(index + 1,rest - nums[index][0] ,1,nums) + nums[index][1];
        }
        else{ // flag == 1 表示上一个 商品, 是 原价 买的 , 那么 当前层, 可以   不买 or 半价买
            ans2 = recursion(index + 1,rest - nums[index][0] / 2,0,nums) + nums[index][1];
        }
        return Math.max(ans1,ans2);
    }


    /*
     感觉 有点 抽象, 我的感觉是不如 记忆化 搜索!
     */
    public int dp(int nums[][],int total){
        int dp[][][] = new int[nums.length + 1][total + 1][2];
        for(int index = nums.length - 1;index >= 0;index--){
            for(int rest = 1; rest <= total;rest++){
                dp[index][rest][0] = Math.max(dp[index + 1][rest][0],dp[index + 1][rest - nums[index][0]][1] + nums[index][1]);
                dp[index][rest][1] = Math.max(dp[index + 1][rest][0],dp[index + 1][rest - nums[index][0] / 2][0] + nums[index][1]);
            }
        }
        return dp[0][total][0];
    }



}
